use std::collections::HashMap;

mod read_json;
use read_json::*;

pub fn count_provinces() -> String {
    let dg = read_json_file();
    println!("{:#?}", dg);

    let mut ans_vec = vec![];
    ans_vec.resize(dg.groups.len(), 0);

    for (number, city_data) in dg.groups.into_iter() {
        // 问题序号
        let number: usize = number.parse().unwrap();
        // println!("- No. {}", number);

        let cities = city_data.city_map;
        let ans = solve_union_find(cities);

        // println!("DEBUG: ans = {ans}");
        // 按顺序输出
        ans_vec[number - 1] = ans;
    }

    // println!("ans vec: {:?}", ans_vec);
    ans_vec
        .into_iter()
        .map(|x| x.to_string())
        .collect::<Vec<String>>()
        .join(",")
}

/// 解决一个并查集问题
fn solve_union_find(cities: HashMap<String, Vec<String>>) -> u32 {
    let mut uf = UnionFind::new();
    for (from, to_list) in cities.into_iter() {
        for to in to_list.into_iter() {
            uf.unite(&from, &to);
        }
    }
    // println!("uf.parent = {:#?}", uf.parent);
    uf.count
}

/// 并查集
#[derive(Default)]
struct UnionFind {
    /** city -> parent */
    parent: HashMap<String, String>,
    count: u32,
}

impl UnionFind {
    pub fn new() -> Self {
        Self::default()
    }

    /// 查询已加入到本结构体的结点的祖先.
    /// 会进行路径压缩.
    pub fn find(&mut self, s: &str) -> String {
        let s_parent = self.parent.get_mut(s).unwrap().clone(); // must has been added
        if s_parent == s {
            return s_parent;
        }

        // 路径压缩
        let new_p = self.find(&s_parent);
        *self.parent.get_mut(s).unwrap() = new_p.clone();
        new_p
    }

    /// 合并两个结点
    pub fn unite(&mut self, s1: &str, s2: &str) {
        self.add_node(&s1);
        self.add_node(&s2);

        let root1 = self.find(&s1);
        let root2 = self.find(&s2);

        if root1 != root2 {
            *self.parent.get_mut(&root1).unwrap() = root2;
            self.count -= 1;
        }
    }

    /// 添加新结点(无视重复)
    fn add_node(&mut self, s: &str) {
        if !self.parent.contains_key(s) {
            self.parent.insert(s.to_string(), s.to_string());
            self.count += 1;
        }
    }
}

// mod tests {
//     use super::*;

//     #[test]
//     fn test_json() {
//         let json_path = "district.json";
//         let file = fs::File::open(json_path).unwrap();
//         let reader = io::BufReader::new(file);

//         #[derive(Debug, Deserialize)]
//         struct DataGroups {
//             #[serde(flatten)]
//             groups: HashMap<String, Vec<(String, Vec<String>)>>,
//         }
//         let dg: DataGroups = serde_json::from_reader(reader).unwrap();
//         println!("{:#?}", dg);
//     }
// }
